#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#define maxn 1000
using namespace std;
int m, n, w[maxn], v[maxn],f[maxn];
/**
 *  dp[i,j]表示背包容量为j时从第1...i个物品中,能取得的最大价值
 *  if(j<w[i])
 *      dp[i][j] = dp[i-1][j];
 *  else 
 *      dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
 * 
 *  使用滚动数组优化:
 *  if(j>w[i])
 *      dp[j] = max(dp[j],dp[j-w[i]]+v[i]); 
 *  这里的d[j]要用到dp[j-w[i]]的数据,并且我们要求这个dp[j-w[i]]实质上就是二维中的dp[i-1][j-w[i]],也就是滚动数组未更新之前的值,如果在循环的时候我们的j是1...n的话就会把之前未更新的值覆盖掉,相当于递推式中的dp[i-1][j-w[i]]被我们无意中改成了dp[i][j-w[i]]了.为了避免覆盖,我们从后向前推就可以避免被覆盖。
 */
int main()
{
    cin >> m >> n;
    for (int i = 1; i <= m; ++i)
    {
        cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= m; ++i)
    {
        for (int j = n; j >= w[i]; --j)
        {
            f[j] = max(f[j], f[j - w[i]] + v[i]);
        }
    }
    printf("%d",f[n]);
    return 0;
};